from collections import deque


class TreeNode:

    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        ans = None

        def f(root):
            if root is None:
                return None
            f(root.left)
            nonlocal ans
            if root.val > p.val and ans is None:
                ans = root
            f(root.right)

        f(root)
        return ans


class Solution:

    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        s = deque()
        node = root
        pre = None
        while len(s) > 0 or node is not None:
            while node is not None:
                s.append(node)
                node = node.left
            c = s.pop()
            if pre == p:
                return c
            pre = c
            node = c.right

        return None
